package  main.java.leetcode.editor.cn;
//2022-05-22 21:41:57
//在 "100 game" 这个游戏中，两名玩家轮流选择从 1 到 10 的任意整数，累计整数和，先使得累计整数和 达到或超过 100 的玩家，即为胜者。 
//
// 如果我们将游戏规则改为 “玩家 不能 重复使用整数” 呢？ 
//
// 例如，两个玩家可以轮流从公共整数池中抽取从 1 到 15 的整数（不放回），直到累计整数和 >= 100。 
//
// 给定两个整数 maxChoosableInteger （整数池中可选择的最大数）和 desiredTotal（累计和），若先出手的玩家是否能稳赢则返回 
//true ，否则返回 false 。假设两位玩家游戏时都表现 最佳 。 
//
// 
//
// 示例 1： 
//
// 
//输入：maxChoosableInteger = 10, desiredTotal = 11
//输出：false
//解释：
//无论第一个玩家选择哪个整数，他都会失败。
//第一个玩家可以选择从 1 到 10 的整数。
//如果第一个玩家选择 1，那么第二个玩家只能选择从 2 到 10 的整数。
//第二个玩家可以通过选择整数 10（那么累积和为 11 >= desiredTotal），从而取得胜利.
//同样地，第一个玩家选择任意其他整数，第二个玩家都会赢。
// 
//
// 示例 2: 
//
// 
//输入：maxChoosableInteger = 10, desiredTotal = 0
//输出：true
// 
//
// 示例 3: 
//
// 
//输入：maxChoosableInteger = 10, desiredTotal = 1
//输出：true
// 
//
// 
//
// 提示: 
//
// 
// 1 <= maxChoosableInteger <= 20 
// 0 <= desiredTotal <= 300 
// 
// Related Topics 位运算 记忆化搜索 数学 动态规划 状态压缩 博弈 👍 420 👎 0

import java.util.HashMap;
import java.util.Map;

class CanIWin {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new CanIWin().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
            if (maxChoosableInteger * (maxChoosableInteger + 1) < (desiredTotal * 2)) {
                return false;
            }
            Map<Integer, Boolean> memory = new HashMap<>(1 << maxChoosableInteger);
            return dfs(maxChoosableInteger, 0, desiredTotal, 0, memory);
        }
        private boolean dfs(int maxChoosableInteger, int state, int desiredTotal, int curTotal, Map<Integer, Boolean> memory) {
            if (!memory.containsKey(state)) {
                boolean ans = false;
                for (int i = 0; i < maxChoosableInteger; i++) {
                    if (((state >> i) & 1) == 1) {
                        continue;
                    }
                    if (curTotal + i + 1 >= desiredTotal) {
                        ans = true;
                        break;
                    }
                    if (!dfs(maxChoosableInteger, state | (1 << i), desiredTotal, curTotal + i + 1, memory)) {
                        ans = true;
                        break;
                    }
                }
                memory.put(state, ans);
            }
            return memory.get(state);
        }
}
//leetcode submit region end(Prohibit modification and deletion)

}
